package Leetcode第二期;

import 多线程.S;

import java.util.Stack;

/**
 * @author : K k
 * @date : 19:35 2020/10/2
 * 给定一个二叉树，判断其是否是一个有效的二叉搜索树。
 *
 * 假设一个二叉搜索树具有如下特征：
 *
 * 节点的左子树只包含小于当前节点的数。
 * 节点的右子树只包含大于当前节点的数。
 * 所有左子树和右子树自身必须也是二叉搜索树。
 * 示例 1:
 *
 * 输入:
 *     2
 *    / \
 *   1   3
 * 输出: true
 * 示例 2:
 *
 * 输入:
 *     5
 *    / \
 *   1   4
 *      / \
 *     3   6
 * 输出: false
 * 解释: 输入为: [5,1,4,null,null,3,6]。
 *      根节点的值为 5 ，但是其右子节点值为 4 。
 */
public class 验证二叉搜索树_98 {

    //思路：二叉搜索树中序遍历的数组是升序的
    public boolean isValidBST(TreeNode root) {
        //中序遍历
        Stack<TreeNode> stack=new Stack<>();
        double orderVal= -Double.MAX_VALUE;;

        while (!stack.isEmpty()||root!=null){
            while (root!=null){
                //指向最左结点
                stack.push(root);
                root=root.left;
            }
            root = stack.pop();
            //进行比较
            if (root.val<=orderVal){
                return false;
            }
            orderVal=root.val;
            root=root.right;
        }
        return true;
    }

    //思路2：左结点上界为root.val，下界为负无穷 ， 右节点上界为正无穷，下界为root.val
    public boolean isValidBSTA(TreeNode root) {
        return helper(root,null,null);
    }

    //左子树的上界为根节点，下界为负无穷， 右子树的上界为正无穷，下界为根节点
    public boolean helper(TreeNode node, Integer lower, Integer upper){
        if(node==null){
            return true;
        }
        int val=node.val;
        if(lower!=null && val<=lower){
            return false;
        }
        if(upper!=null && val>=upper){
            return false;
        }
        if(!helper(node.right,val,upper)){
            return false;
        }
        if(!helper(node.left,lower,val)){
            return false;
        }
        return true;

    }
}
